package com.shujia.wyh.day23;

/*
        兔子问题(斐波那契数列) 不死神兔
            有一对兔子，从出生第三个月开始，每个月都生一对兔子
            小兔子长到三个月后又每个月生一对兔子，假设这些兔子都不会死
            问：第20个月，有多少对兔子？

        寻找规律：
            月            对数
            1              1
            2              1
            3              2
            4              3
            5              5
            6              8
            7              13
            ...
       由此可见，兔子的对数数量：
       1，1，2，3，5，8，13，21，34....
       发现的规律是：
        1、从第三项开始，每一项都是前两项之和
        2、说明每一项的前两项数据是已知的


      如何实现：
        1、使用数组实现
        2、基本变量实现
        3、递归实现

 */
public class DiGuiDemo3 {
    public static void main(String[] args) {
        //使用数组实现
        int[] arr = new int[20];
        arr[0] = 1;
        arr[1] = 1;
//        arr[2] = arr[0]+arr[1];
//        arr[3] = arr[1]+arr[2];
//        arr[4] = arr[2]+arr[3];
//        //...
//        arr[19] = arr[17]+arr[18];
        //使用循环改进
        for (int i = 2; i < arr.length; i++) {
            arr[i] = arr[i - 2] + arr[i - 1];
        }
        System.out.println("第20个月的时候，兔子对数为：" + arr[19]);
        System.out.println("====================================");
        //基本变量实现
        //定义两个变量表示相邻的两项
        //第1个相邻的数据： a=1,b=1;
        //第2个相邻的数据： a=1,b=2;
        //第3个相邻的数据： a=2,b=3;
        //第4个相邻的数据： a=3,b=5;
        //第5个相邻的数据： a=5,b=8;
        //第6个相邻的数据： a=8,b=13;
        //...
        //规律：
        //下一次的相邻数据a是上一次相邻数据b的值，下一次相邻数据b是上一次a+b的值
        int a = 1;
        int b = 1;
        for (int i = 0; i < 18; i++) {
            //定义一个临时变量，保存上一次的a的值
            int temp = a;
            a = b;
            b = temp + b;
        }
        System.out.println("第20个月的时候，兔子对数为：" + b);
        System.out.println("=======================================");
        //使用递归实现
        int result = fibonacci(20);
        System.out.println("第20个月的时候，兔子对数为：" + result);
    }

    /*
        递归实现：
            1、结束条件是什么？
                当月份是1或者2的时候，return 1;
            2、递归的逻辑是：
                从第三个月到第20个月，每一个月是前两个月之和。
     */
    public static int fibonacci(int month) { // 5
        if (month == 1 || month == 2) {
            return 1;
        } else {
            //fibonacci(4) + fibonacci(3)
            //fibonacci(3) + fibonacci(2) + fibonacci(2) + fibonacci(1)
            //fibonacci(2) + fibonacci(1) + fibonacci(2) + fibonacci(2) + fibonacci(1)
            //1 + 1 + 1 + 1 + 1 = 5
            return fibonacci(month - 1) + fibonacci(month - 2);
        }
    }
}







